package dailyTopic;

import java.util.Arrays;

/**
 * @author zhangmin
 * @create 2021-08-04 9:55
 */
public class triangleNumber611 {
    //1.排序+二分
    //2.排序+双指针: 循环i，在i之后设置j和k双指针
    /*public int triangleNumber(int[] nums) {
        int n=nums.length;
        Arrays.sort(nums);
        int res=0;
        for (int i=0;i<n-1;i++){
            for (int j = i+1; j < n-1; j++) {
                int l=j+1,r=n-1;
                int k=j;
                while (l<=r){
                    int mid=l+(r-l)/2;
                    if (nums[mid]<nums[i]+nums[j]){
                        k=mid;
                        l=mid+1;
                    }else {
                        r=mid-1;
                    }
                }
                res+=(k-j);
            }
        }
        return res;
    }*/

    public int triangleNumber(int[] nums) {
        int n=nums.length;
        Arrays.sort(nums);
        int res=0;
        for (int i = 0; i < n; i++) {
            for (int j = i-1,k=0; k<j; j--) {
                while (k<j&&nums[k]+nums[j]<=nums[i]){
                    k++;
                }
                res+=j-k;
            }
        }
        return res;
    }



    public static void main(String[] args) {
        int[] nums = new int[]{2,2,3,4};
        triangleNumber611 object = new triangleNumber611();
        System.out.println(object.triangleNumber(nums));
    }

}
